package pers.sloera.leetcode.splitIntoFibonacci;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Stack;

/**
 * 842. 将数组拆分成斐波那契序列
 * <p>
 * <p>
 * 给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
 * <p>
 * 形式上，斐波那契式序列是一个非负整数列表 F，且满足：
 * <p>
 * 0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
 * F.length >= 3；
 * 对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
 * 另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
 * <p>
 * 返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
 *
 * @author SloeraN
 * @version 1.0
 * @class pers.sloera.leetcode.splitIntoFibonacci.Solution
 * @date 2020/12/8
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.splitIntoFibonacci("1320581321313221264343965566089105744171833277577"));
    }

    public List<Integer> splitIntoFibonacci(String input) {
        ArrayList<Integer> result = new ArrayList<>();
        if (input.length() < 3) {
            return result;
        }
        // 0 1 2 3 从 2开始
        int startIndex = input.length() / 3 * 2;
        // 最后一个数字，长度肯定不能超过1/3的字符串长度。从2/3处开始判断，直到长度为1
        for (; startIndex < input.length(); startIndex++) {
            ArrayList<Integer> temp = new ArrayList<>();
            Stack<String> indexStack = new Stack<>();
            String substring = input.substring(startIndex);
            indexStack.push(substring);
            if (findNextIndex(substring, input.substring(0, startIndex), indexStack)) {
                System.out.println(indexStack);
                while (!indexStack.empty()) {
                    result.add(Integer.valueOf(indexStack.pop()));
                }
                return result;
            }
        }

        return result;
    }

    // 123456 789
    private boolean findNextIndex(String origin, String sequenceString, Stack<String> indexStack) {
        // 避免00
        // integer存在NumberFormatException溢出

        // if (Pattern.matches("[0]{2,}", origin)) {
        //     return false;
        // }
        // if (new BigInteger(origin).equals(new BigInteger("0")) && origin.length() > 1) {
        //     return false;
        // }
        try {
            Integer.valueOf(origin);
        } catch (NumberFormatException e) {
            return false;
        }
        if (Integer.valueOf(origin).equals(0) && origin.length() > 1) {
            return false;
        }

        // 从6尝试到456
        // 避免right out of range
        for (int i = 1; i <= origin.length() && i < sequenceString.length(); i++) {
            String right = sequenceString.substring(sequenceString.length() - i);
            // int left = new BigInteger(origin).subtract(new BigInteger(right)).intValue();
            int left = 0;
            try {
                left = Integer.valueOf(origin) - Integer.valueOf(right);
            } catch (NumberFormatException e) {
                continue;
            }
            if (left < 0) {
                continue;
            }
            // 下一个截取
            String nextSequence = sequenceString.substring(0, sequenceString.length() - i);
            // 剩余数小于差，此路不通
            // 不可用Integer，避免溢出
            if (nextSequence.length() < String.valueOf(left).length()) {
                continue;
            }
            if (nextSequence.endsWith(String.valueOf(left))) {
                indexStack.push(right);
                // 查询完所有字符说明匹配
                if (Objects.equals(left + right, sequenceString)) {
                    indexStack.push(String.valueOf(left));
                    return true;
                }
                if (findNextIndex(right, nextSequence, indexStack)) {
                    return true;
                } else {
                    indexStack.pop();
                    continue;
                }
            }
        }
        return false;
    }

}
